package leetcode.D200.T200;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-26 12:07:19 星期六
 */

class Solution {
    private static int[][] dirs = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length, num = 0;
        boolean[][] visited = new boolean[m][n];
        for(int i=0; i<m; ++i) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    num++;
                    dfs(grid, visited, i, j);
                }
            }
        }
        return num;
    }

    private void dfs(char[][] grid, boolean[][] visited, int i, int j) {
        visited[i][j] = true;
        for (int[] dir : dirs) {
            if (isValid(grid, visited, i+dir[0], j+dir[1]))
                dfs(grid, visited, i+dir[0], j+dir[1]);
        }
    }

    private boolean isValid(char[][] grid, boolean[][] visited, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length)
            return false;
        if (grid[x][y] == '0' || visited[x][y])
            return false;
        return true;
    }
}